package org.lql.algo.codecrush.hot100.binarySearch;

import java.util.Arrays;

/**
 * @author: liangqinglong
 * @date: 2025-09-05 14:01
 * @description: 34. 在排序数组中查找元素的第一个和最后一个位置 <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class SearchRange {

	public int[] searchRange(int[] nums, int target) {
		// 开始位置：第一个>=target
		// 结束位置：最后一个<=target
		int left = 0;
		int right = nums.length;
		int[] ans = new int[2];
		while (left < right) {
			int mid = (left + right) >> 1;
			if (nums[mid] >= target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		ans[0] = right;
		left = -1;
		right = nums.length - 1;
		while (left < right) {
			int mid = (left + right + 1) >> 1;
			if (nums[mid] <= target) {
				left = mid;
			} else {
				right = mid - 1;
			}
		}
		ans[1] = right;
		if (ans[0] > ans[1]) {
			return new int[]{-1, -1};
		}
		return ans;
	}

	public static void main(String[] args) {
		SearchRange searchRange = new SearchRange();
		int[] nums = {5, 7, 7, 8, 8, 10};
		int target = 8;
		System.out.println(Arrays.toString(searchRange.searchRange(nums, target)));
	}
}
